module Arbol23 where

data Arbol23 a b = Hoja a | Dos b (Arbol23 a b) (Arbol23 a b) | Tres b b (Arbol23 a b) (Arbol23 a b) (Arbol23 a b)
    deriving Eq
{- Funciones para mostrar el Arbol. -}

instance (Show a, Show b) => Show (Arbol23 a b) where
    show x = concatMap (++"\n") (padTree 0 x)

padTree:: (Show a, Show b) => Int -> (Arbol23 a b)-> [String]
padTree i (Hoja x) = [(pad i) ++  (show x)]
padTree i (Dos x a1 a2) = [(pad i) ++  (show x) ] ++ (concatMap (padTree (i + 4)) [a1,a2])
padTree i (Tres x y a1 a2 a3) = [(pad i) ++  (show x) ++ (' ':(show y))] ++ (concatMap (padTree (i + 4)) [a1,a2,a3])

pad:: Int -> String
pad i = replicate i ' '

{- Funciones pedidas. -}

foldA23::(a->c)->(b->c->c->c)->(b->b->c->c->c->c)->Arbol23 a b->c
foldA23 fHoja fDos fTres arbol = case arbol of
    Hoja n -> fHoja n
    Dos n a1 a2 -> fDos n (rec a1) (rec a2)
    Tres n m a1 a2 a3 -> fTres n m (rec a1) (rec a2) (rec a3)
    where rec = foldA23 fHoja fDos fTres

--Lista en preorden de los internos del Arbol.
internos::Arbol23 a b->[b]
internos = foldA23 (const []) (\b intL intR -> b:(intL ++ intR)) (\b1 b2 intL intM intR -> b1:b2:(intL ++ intM ++ intR))

--Lista las hojas de izquierda a derecha.
hojas::Arbol23 a b->[a]
hojas = foldA23 (\a -> [a]) (\b hojasL hojasR -> hojasL ++ hojasR) (\b1 b2 hojasL hojasM hojasR -> hojasL ++ hojasM ++ hojasR)

--Indica si un árbol es hoja
esHoja::Arbol23 a b->Bool
esHoja a = case a of
            Hoja _ -> True
            Dos _ _ _ -> False
            Tres _ _ _ _ _ -> False

{- Un map para Arbol23, aplica la primer función a todas
   las hojas y la otra a los elementos de los nodos internos. -}
mapA23::(a->c)->(b->d)->Arbol23 a b->Arbol23 c d
mapA23 fH fI = foldA23 (\a -> Hoja (fH a)) (\b rL rR -> Dos (fI b) rL rR) (\b1 b2 rL rM rR-> Tres (fI b1) (fI b2) rL rM rR)

{- Trunca el Arbol hasta un determinado nivel. 
   Cuando llega a 0, reemplaza el resto del Arbol por una hoja
   con el valor indicado. Funciona para Arboles infinitos. -}
truncar::a->Integer->Arbol23 a b->Arbol23 a b
truncar e n = flip auxTruncar n
    where   auxTruncar = foldA23    (\a i-> truncarODevolver i (Hoja a))
                                    (\b rL rR i -> truncarODevolver i (Dos b (rL (i-1)) (rR (i-1))))
                                    (\b1 b2 rL rM rR i -> truncarODevolver i (Tres b1  b2 (rL (i-1)) (rM (i-1)) (rR (i-1))))
            truncarODevolver i arbol = if (i == 0) then Hoja e else arbol

{- Evalúa las funciones tomando los valores de los hijos como argumentos.
   En el caso de que haya 3 hijos, asocia a izquierda. -}
evaluar::Arbol23 a (a->a->a)->a
evaluar = foldA23 id (\f rL rR -> f rL rR) (\f1 f2 rL rM rR -> f2 (f1 rL rM) rR)
